A Hybrid Meta-Heuristic for Multi-Objective Optimization: MOSATS

Real optimization problems often involve not one, but multiple objectives, usually in conflict. In single-objective optimization there exists a global optimum, while in the multi-objective case no optimal solution is clearly defined but rather a set of solutions, called the Pareto-optimal front. Thus, the goal of multi-objective strategies is to generate a set of non-dominated solutions as an approximation to this front. However, the majority of problems of this kind cannot be solved exactly because they have very large and highly complex search spaces. In recent years, meta-heuristics have become important tools for solving multi-objective problems encountered in industry as well as in the theoretical field. This paper presents a novel approach based on hybridizing Simulated Annealing and Tabu Search. Experiments on the Graph Partitioning Problem show that this new method is a better tool for approximating the efficient set than other strategies also based on these meta-heuristics.     

地表发射率的机载傅里叶变换红外光谱反演方法研究

介绍了利用机载傅里叶变换红外(FTIR)光谱仪测量地球、大气辐射的实验过程,并对由光谱仪测得的辐射与地表光谱发射率、大气透过率等参数的关系进行了深入的分析,给出了理论表达式。提出了一种基于梯度搜索的优化方法,即由机载FTIR光谱仪测得的辐亮度光谱反演得到方差最小的光谱发射率最优解。反演结果表明,在中红外波段,沙地平均光谱发射率为0.70,裸土地表平均光谱发射率为0.95。     

一类共轭梯度法的全局收敛性

共轭梯度法是求解大规模元约束优化同题的一种有效方法，本文提出一种新的共轭梯度法，证明了在推广的Wolfe线搜索条件下方法具有全局收敛性。最后对算法进行了数值试验，试验结果表明该算法具有良好的收敛性和有效性。     

Optimizing heuristic search in forest planning

Heuristic search methods are being used more and more in forest planning since the current formulations of exact methods such as linear programming are not suitable to all today's planning problems. A practical problem with most heuristics is that their performance greatly depends on the parameters that guide their search process. The effect of parameters is hard to know without extensive tests, but these tests cannot be conducted in forest planning practice, because of lacking time and experience. This study presented a method that uses Hooke and Jeeves direct search to optimize the parameters of a heuristic, taking into account the allowed computing time. The method was used to optimize three local-improvement heuristics in a non-spatial and a spatial forest planning problem, and with a short and long computing time. The heuristics were simulated annealing, threshold accepting, and tabu search, all of which are used in forestry. The results were logical and showed that while the optimal values of some parameters were rather constant the others were sensitive to problem type, allowed computing time, or problem size. The objective function value of the forest planning problem was not sensitive to small changes in the parameters of the heuristics. However, because computing time was very sensitive to many parameters, there was not much freedom to set the parameters if both the quality of the solution and speed of the algorithm had to be maintained.     

一种新线搜索下的FR共轭梯度法

基于传统的Wolfe线搜索,提出了一种新的非精确线搜索．在无需限制参数σ≤1/2的情况下(即盯的取值范围扩展至0＜σ＜1),证明了FR算法的全局收敛性．数值实验表明了这种线搜索下的FR算法的有效性．     

AN ADAPTIVE NONMONOTONIC TRUST REGION METHOD WITH CURVILINEAR SEARCHES

In this paper,an algorithm for unconstrained optimization that employs both trustregion techniques and curvilinear searches is proposed.At every iteration,we solve thetrust region subproblem whose radius is generated adaptively only once.Nonmonotonicbacktracking curvilinear searches are performed when the solution of the subproblem isunacceptable.The global convergence and fast local convergence rate of the proposedalgorithms are established under some reasonable conditions.The results of numericalexperiments are reported to show the effectiveness of the proposed algorithms.     

An electromagnetic meta-heuristic for the nurse scheduling problem

In this paper, we present a novel meta-heuristic technique for the nurse scheduling problem (NSP). This well-known scheduling problem assigns nurses to shifts per day maximizing the overall quality of the roster while taking various constraints into account. The problem is known to be NP-hard. Due to its complexity and relevance, many algorithms have been developed to solve practical and often case-specific models of the NSP. The huge variety of constraints and the several objective function possibilities have led to exact and meta-heuristic procedures in various guises, and hence comparison and state-of-the-art reporting of standard results seem to be a utopian idea. We present a meta-heuristic procedure for the NSP based on the framework proposed by Birbil and Fang (J. Glob. Opt. 25, 263–282, 2003). The Electromagnetic (EM) approach is based on the theory of physics, and simulates attraction and repulsion of sample points in order to move towards a promising solution. Moreover, we present computational experiments on a standard benchmark dataset, and solve problem instances under different assumptions. We show that the proposed procedure performs consistently well under many different circumstances, and hence, can be considered as robust against case-specific constraints.     

GLOBAL CONVERGENCE RESULTS OF A THREE TERM MEMORY GRADIENT METHOD WITH A NON-MONOTONE LINE SEARCH TECHNIQUE

In this paper, a new class of three term memory gradient method with nonmonotone line search technique for unconstrained optimization is presented. Global convergence properties of the new methods are discussed. Combining the quasi-Newton method with the new method, the former is modified to have global convergence property. Numerical results show that the new algorithm is efficient.     

The vehicle routing problem with flexible time windows and traveling times

We generalize the standard vehicle routing problem by allowing soft time window and soft traveling time constraints, where both constraints are treated as cost functions. With the proposed generalization, the problem becomes very general. In our algorithm, we use local search to determine the routes of vehicles. After fixing the route of each vehicle, we must determine the optimal start times of services at visited customers. We show that this subproblem is NP-hard when cost functions are general, but can be efficiently solved with dynamic programming when traveling time cost functions are convex even if time window cost functions are non-convex. We deal with the latter situation in the developed iterated local search algorithm. Finally we report computational results on benchmark instances, and confirm the benefits of the proposed generalization.